/**
 * @author zhangmin
 * @create 2022-09-20 14:51
 * 百度、快手二面
 * 给你一个数组，将数组中的奇数调整到偶数前面，并且奇数偶数内部保持相对顺序不变，在原数组上操作
 * 1、遍历两遍，分别用新数组记录奇数和偶数--时间O（n）、空间O（n）
 * 2、原地，遍历元素，遇到奇数时，将奇数前面的偶数部分后一一位，然后将奇数放到偶数的前面
 */
public class reOrderArray {
    public static void main(String[] args) {
        int[] nums=new int[]{1,4,5,3,7,8,0,9};
        int p=0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i]%2==1){
                int temp=nums[i];
                int j=i;
                //移动[p,j]直接的偶数，后移一位
                while (j>p){
                    nums[j]=nums[j-1];
                    j--;
                }
                nums[p++]=temp;
            }
        }
        for (int i = 0; i < nums.length; i++) {
            System.out.print(nums[i]+" ");
        }
    }
}
